package com.dong.ListNode.arithemtic;

/**
 * @Classname ListNodeDemo4
 * @Description 翻转链表
 * @Date 2022/4/10 10:17
 * @Author dcz
 */
public class ListNodeDemo4 {

    public ListNode reverseList2(ListNode head) {
        return reverse(null,head) ;
    }

    //双指针法
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur!=null) {
            temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }

    //递归法
    private  ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        // 先保存下一个节点
        temp = cur.next;
        // 反转
        cur.next = prev;
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}
